package 剑指offer;

import 抽象数据类型.TreeNode;

import java.util.LinkedList;

/**
 * @description:
 * @author: ywk
 * @date: 2020-10-26
 */
public class 输出二叉树的右视图 {


    public static void main(String[] args) {
        int[] xianxu = {1, 2, 4, 5, 6, 3};
        int[] zhongxu = {5, 4, 6, 2, 1, 3};
        int[] solve = solve(xianxu, zhongxu);
        System.out.println(solve);
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     *
     * @param xianxu  int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public static int[] solve(int[] xianxu, int[] zhongxu) {
        // write code her
        TreeNode root = reback(xianxu, zhongxu, 0, xianxu.length, 0, xianxu.length);
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        LinkedList<Integer> arr = new LinkedList<>();
        queue.offer(root);
        while (queue.size() != 0) {
            int size = queue.size();
            while (size-- > 0) {
                TreeNode poll = queue.poll();
                if (poll.getLeft() != null) {
                    queue.offer(poll.getLeft());
                }
                if (poll.getRight() != null) {
                    queue.offer(poll.getRight());
                }
                if (size == 0) {
                    arr.add((Integer) poll.val);
                }
            }
        }

        int[] resultArr = new int[arr.size()];
        for (int i = 0; i < arr.size(); i++) {
            resultArr[i] = arr.get(i);
        }
        return resultArr;
    }
    //根据前序和中序还原一颗二叉树
    public static TreeNode reback(int[] xianxu, int[] zhongxu, int preStart, int preEnd, int midStart, int midEnd) {
        if (preStart == preEnd) {
            return null;
        }
        TreeNode root = new TreeNode(xianxu[preStart]);
        int mid = findIndex(zhongxu, xianxu[preStart], midStart, midEnd);
        int leftNum = mid - midStart;
        root.setLeft(reback(xianxu, zhongxu, preStart + 1, preStart + leftNum + 1, midStart, mid));
        root.setRight(reback(xianxu, zhongxu, preStart + leftNum + 1, preEnd, mid + 1, midEnd));
        return root;

    }

    public static int findIndex(int[] arr, int tar, int start, int end) {
        for (int i = start; i < end; i++) {
            if (arr[i] == tar) {
                return i;
            }
        }
        return -1;
    }
}
